


class BTree:

    def __init__(self, data=None, left=None, right=None):  # 初始化
        self.data = data   # 数据域
        self.left = left  # 左子树
        self.right = right  # 右子树
        # self.dot = Digraph

    # 前序遍历
    def pre_order(self):
        if self.data is not None:
            print(self.data, end=" ")
        if self.left is not None:
            self.left.pre_order()
        if self.right is not None:
            self.right.pre_order()

    # 中序遍历
    def in_order(self):
        if self.left is not None:
            self.left.in_order()
        if self.data is not None:
            print(self.data, end=" ")
        if self.right is not None:
            self.right.in_order()

    # 后序遍历
    def post_order(self):
        if self.left is not None:
            self.left.post_order()
        if self.right is not None:
            self.right.post_order()
        if self.data is not None:
            print(self.data, end=" ")

    # 层次遍历
    def level_order(self):
        def l_child_of_node(node):  # 返回某个节点的左孩子
            return node.left if node.left is not None else None
        def r_child_of_node(node):  # 返回某个节点的右孩子
            return node.right if node.right is not None else None

        level_order = []  # 层序遍历列表
        if self.data is not None:
            level_order.append([self])

        height = self.height()
        if height >= 1:
            for _ in range(2, height + 1):  # 对第二层及其以后的层数进行操作，在level_order中添加节点而不是数据
                level = []  # 该层的节点
                for node in level_order[-1]:
                    if l_child_of_node(node):  # 如果左孩子为空
                        level.append(l_child_of_node(node))
                    if
